﻿//我的（超时了QAQ）
class Solution {
public:
	vector<int> missingTwo(vector<int>& nums) {
		int N = nums.size() + 2;
		vector<int> ret(2, 0);

		//先找到第一个缺失的数字
		for (int i = 1; i <= N; i++) {
			if (count(nums.begin(), nums.end(), i) == 0)
			{
				ret[0] = i;
				break;
			}
		}

		for (int i = 0; i < nums.size(); i++) {
			ret[1] ^= nums[i];
		}
		ret[1] ^= ret[0];

		for (int i = 1; i <= N; i++) {
			ret[1] ^= i;
		}
		return ret;
	}
};


//答案
class Solution
{
public:
	vector<int> missingTwo(vector<int>& nums)
	{
		// 1. 将所有的数异或在⼀起
		int tmp = 0;
		for (auto x : nums) tmp ^= x;
		for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
		// 2. 找出 a，b 中⽐特位不同的那⼀位
		int diff = 0;
		while (1)
		{
			if (((tmp >> diff) & 1) == 1) break;
			else diff++;
		}
		// 3. 根据 diff 位的不同，将所有的数划分为两类来异或
		int a = 0, b = 0;
		for (int x : nums)
			if (((x >> diff) & 1) == 1) b ^= x;
			else a ^= x;
		for (int i = 1; i <= nums.size() + 2; i++)
			if (((i >> diff) & 1) == 1) b ^= i;
			else a ^= i;
		return { a, b };
	}
};